package bTree.LeetCode;

public class N皇后2 {
    int cnt=0;
    public int totalNQueens(int n) {
        char[][]classBoard=new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int i1 = 0; i1 < n; i1++) {
                classBoard[i][i1]='.';
            }
        }
        int row=0;
        backtacking(classBoard,n,0);
        return cnt;
    }

    private void backtacking(char[][] classBoard, int n, int row) {
        if(row==n){
            cnt++;
            return;
        }
        char[] chars = classBoard[row];
        for (int i=0;i<n;i++){
            chars[i]='Q';
            if(isValid(classBoard,n,row,i)){
                backtacking(classBoard,n,row+1);
            }
            chars[i]='.';
        }
    }

    private boolean isValid(char[][] classBoard, int n, int row, int line) {
        for (int i1 = 0; i1 < n; i1++) {
            if(classBoard[i1][line]=='Q'&&i1!=row){
                return false;
            }
            int line2=line+1;
            for(int r=row-1;r>=0;r--){
                if(line2>=n){
                    break;
                }
                if(classBoard[r][line2]=='Q'){
                    return false;
                }
                line2++;
            }
            int line3=line-1;
            for(int r=row-1;r>=0;r--){
                if(line3<0){
                    break;
                }
                if(classBoard[r][line3]=='Q'){
                    return false;
                }
                line3--;
            }
        }
        return true;
    }
}